home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / gif_lib.arc / GIF_HASH.C < prev    next >
C/C++ Source or Header  |  1991-03-02  |  5KB  |  145 lines
  1. /*****************************************************************************
  2. *   "Gif-Lib" - Yet another gif library.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber            IBM PC Ver 0.1,    Jun. 1989    *
  5. ******************************************************************************
  6. * Module to support the following operations:                     *
  7. *                                         *
  8. * 1. InitHashTable - initialize hash table.                     *
  9. * 2. ClearHashTable - clear the hash table to an empty state.             *
  10. * 2. InsertHashTable - insert one item into data structure.             *
  11. * 3. ExistsHashTable - test if item exists in data structure.             *
  12. *                                         *
  13. * This module is used to hash the GIF codes during encoding.             *
  14. ******************************************************************************
  15. * History:                                     *
  16. * 14 Jun 89 - Version 1.0 by Gershon Elber.                     *
  17. *****************************************************************************/
  18.  
  19. #include <io.h>
  20. #include <fcntl.h>
  21. #include <stdio.h>
  22. #include <string.h>
  23. #include <alloc.h>
  24. #include <sys\stat.h>
  25. #include "gif_lib.h"
  26. #include "gif_hash.h"
  27.  
  28. #define PROGRAM_NAME    "GIF_LIBRARY"
  29. #define VERSION        "ß Version 1.0, "
  30.  
  31. /* #define  DEBUG_HIT_RATE  /* Debug number of misses per hash Insert/Exists */
  32.  
  33. #ifdef    DEBUG_HIT_RATE
  34. static long NumberOfTests = 0,
  35.         NumberOfMisses = 0;
  36. #endif    DEBUG_HIT_RATE
  37.  
  38. static char *VersionStr =
  39.     PROGRAM_NAME
  40.     "    IBMPC "
  41.     VERSION
  42.     "    Gershon Elber,    "
  43.     __DATE__ ",   " __TIME__ "\n"
  44.     "(C) Copyright 1989 Gershon Elber, Non commercial use only.\n";
  45.  
  46. static int KeyItem(unsigned long Item);
  47.  
  48. /******************************************************************************
  49. * Initialize HashTable - allocate the memory needed and clear it.          *
  50. ******************************************************************************/
  51. GifHashTableType *_InitHashTable(void)
  52. {
  53.     GifHashTableType *HashTable;
  54.  
  55.     if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType)))
  56.     == NULL)
  57.     return NULL;
  58.  
  59.     _ClearHashTable(HashTable);
  60.  
  61.     return HashTable;
  62. }
  63.  
  64. /******************************************************************************
  65. * Routine to clear the HashTable to an empty state.                  *
  66. * This part is a little machine depended. Use the commented part otherwise.   *
  67. ******************************************************************************/
  68. void _ClearHashTable(GifHashTableType *HashTable)
  69. {
  70.     memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(long));
  71. }
  72.  
  73. /******************************************************************************
  74. * Routine to insert a new Item into the HashTable. The data is assumed to be  *
  75. * new one.                                      *
  76. ******************************************************************************/
  77. void _InsertHashTable(GifHashTableType *HashTable, unsigned long Key, int Code)
  78. {
  79.     int HKey = KeyItem(Key);
  80.     unsigned long *HTable = HashTable -> HTable;
  81.  
  82. #   ifdef DEBUG_HIT_RATE
  83.     NumberOfTests++;
  84.     NumberOfMisses++;
  85. #   endif DEBUG_HIT_RATE
  86.  
  87.     while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) {
  88. #    ifdef DEBUG_HIT_RATE
  89.         NumberOfMisses++;
  90. #    endif DEBUG_HIT_RATE
  91.     HKey = (HKey + 1) & HT_KEY_MASK;
  92.     }
  93.     HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code);
  94. }
  95.  
  96. /******************************************************************************
  97. * Routine to test if given Key exists in HashTable and if so returns its code *
  98. * Returns the Code if key was found, -1 if not.                      *
  99. ******************************************************************************/
  100. int _ExistsHashTable(GifHashTableType *HashTable, unsigned long Key)
  101. {
  102.     int HKey = KeyItem(Key);
  103.     unsigned long *HTable = HashTable -> HTable, HTKey;
  104.  
  105. #   ifdef DEBUG_HIT_RATE
  106.     NumberOfTests++;
  107.     NumberOfMisses++;
  108. #   endif DEBUG_HIT_RATE
  109.  
  110.     while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) {
  111. #    ifdef DEBUG_HIT_RATE
  112.         NumberOfMisses++;
  113. #    endif DEBUG_HIT_RATE
  114.     if (Key == HTKey) return HT_GET_CODE(HTable[HKey]);
  115.     HKey = (HKey + 1) & HT_KEY_MASK;
  116.     }
  117.  
  118.     return -1;
  119. }
  120.  
  121. /******************************************************************************
  122. * Routine to generate an HKey for the hashtable out of the given unique key.  *
  123. * The given Key is assumed to be 20 bits as follows: lower 8 bits are the     *
  124. * new postfix character, while the upper 12 bits are the prefix code.          *
  125. * Because the average hit ratio is only 2 (2 hash references per entry),      *
  126. * evaluating more complex keys (such as twin prime keys) does not worth it!   *
  127. ******************************************************************************/
  128. static int KeyItem(unsigned long Item)
  129. {
  130.     return ((Item >> 12) ^ Item) & HT_KEY_MASK;
  131. }
  132.  
  133. #ifdef    DEBUG_HIT_RATE
  134. /******************************************************************************
  135. * Debugging routine to print the hit ratio - number of times the hash table   *
  136. * was tested per operation. This routine was used to test the KeyItem routine *
  137. ******************************************************************************/
  138. void HashTablePrintHitRatio(void)
  139. {
  140.     printf("Hash Table Hit Ratio is %ld/%ld = %ld%%\n",
  141.     NumberOfMisses, NumberOfTests,
  142.     NumberOfMisses * 100 / NumberOfTests);
  143. }
  144. #endif    DEBUG_HIT_RATE
  145.